<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>

  <body>
    <script>
      var reverseList = function (head) {
        // 方法一：使用外部空间反转之后再赋值给原来的链表（）---时间：O（3n）---空间：O（n+2）（n是数组的长度）
        // let arr = []
        // let curr1 = head
        // let curr2 = head
        // while (curr1) {
        //   arr.push(curr1.val)
        //   curr1 = curr1.next
        // }
        // arr.reverse()
        // while (curr2) {
        //   curr2.val = arr.shift()
        //   curr2 = curr2.next
        // }
        // return head
        
        // 方法二：双指针遍历（）---时间：O（n）---空间：O（1）
        // let prev = null;
        // let curr = head;
        // while (curr) {
        //   const temp = curr.next;
        //   curr.next = prev;
        //   prev = curr;
        //   curr = temp;
        // }
        // return prev

        // 方法三：递归（https://leetcode.cn/problems/reverse-linked-list/solutions/36710/dong-hua-yan-shi-206-fan-zhuan-lian-biao-by-user74/?orderBy=hot）---时间：O（n）---空间：O（1）
        if (!head || !head.next) {
          return head;
        }
        // curr一直是最后一个节点
        let curr = reverseList(head.next);
        head.next.next = head;
        // 防止死循环，先断开
        head.next = null;
        return curr;
      };
    </script>
  </body>
</html>
